import java.util.Random;
import java.util.Vector;

public class Algorithms {

	public static byte[][] createNewMatrix() {
		Random random = new Random();
		byte[][] a = new byte[9][9];

		int i, j, remain, count;

		for (i = 0; i < 9; i++)
			for (j = 0; j < 9; j++)
				a[i][j] = 0;

		count = 81;
		boolean stop;
		do {
			remain = random.nextInt(count--) + 1;
			stop = false;
			for (i = 0; i < 9; i++) {
				if (stop)
					break;
				for (j = 0; j < 9; j++)
					if (a[i][j] == 0) {
						remain--;
						if (remain == 0) {
							a[i][j] = (byte) (random.nextInt(7) + 1);
							stop = true;
							break;
						}
					}
			}
		} while (count > 76);

		addNextColor(a);

		return a;
	}

	public static void addNextColor(byte[][] a) {
		Random random = new Random();
		int count = countEmpty(a);
		int tmp, i, j, remain;
		boolean stop;

		for (tmp = 0; tmp < 3; tmp++) {
			remain = random.nextInt(count--) + 1;
			stop = false;
			for (i = 0; i < 9; i++) {
				if (stop)
					break;
				for (j = 0; j < 9; j++)
					if (a[i][j] == 0) {
						remain--;
						if (remain == 0) {
							a[i][j] = (byte) -(random.nextInt(7) + 1);
							stop = true;
							break;
						}
					}
			}
		}
	}

	public static int countEmpty(byte[][] a) {
		int i, j, count = 0;
		for (i = 0; i < 9; i++)
			for (j = 0; j < 9; j++)
				if (a[i][j] <= 0)
					count++;
		return count;
	}

	public static Vector havePath(byte[][] a, int i1, int j1, int i2, int j2) {
		byte[][] dadi = new byte[9][9];
		byte[][] dadj = new byte[9][9];

		byte[] queuei = new byte[81];
		byte[] queuej = new byte[81];
		
		byte[] u = { 1, 0, -1, 0 };
		byte[] v = { 0, 1, 0, -1 };

		byte fist = 0, last = 0;

		for (int x = 0; x < 9; x++)
			for (int y = 0; y < 9; y++)
				dadi[x][y] = -1;

		queuei[0] = (byte) i2;
		queuej[0] = (byte) j2;
		dadi[i2][j2] = -2;

		while (fist <= last) {
			byte x = queuei[fist];
			byte y = queuej[fist];
			fist++;
			for (int k = 0; k < 4; k++) {
				byte xx = (byte) (x + u[k]);
				byte yy = (byte) (y + v[k]);
				if (xx == i1 && yy == j1) {
					dadi[i1][j1] = x;
					dadj[i1][j1] = y;
					return buildPath(dadi, dadj, i1, j1);
				}
				if (!isInside(xx, yy)) continue;
				if (dadi[xx][yy] == -1 && a[xx][yy] <= 0) {
					last++;
					queuei[last] = xx;
					queuej[last] = yy;
					dadi[xx][yy] = x;
					dadj[xx][yy] = y;
				}
			}
		}
		return null;
	}

	public static Vector buildPath(byte[][] dadi, byte[][] dadj, int i1, int j1) {
		Vector path = new Vector();
		int k;
		while (true) {
			path.addElement(new Point(i1, j1));
			k = i1;
			i1 = dadi[i1][j1];
			if (i1 == -2) break;
			j1 = dadj[k][j1];
		}
		return path;
	}

	public static Vector checkLines(byte[][] a, int iCenter, int jCenter) {
		Vector lines = new Vector();

		int[] u = { 0, 1, 1, 1 };
		int[] v = { 1, 0, -1, 1 };
		int i, j, k;
		for (int t = 0; t < 4; t++) {
			k = 0;
			i = iCenter;
			j = jCenter;
			while (true) {
				i += u[t];
				j += v[t];
				if (!isInside(i, j))
					break;
				if (a[i][j] != a[iCenter][jCenter])
					break;
				k++;
			}
			i = iCenter;
			j = jCenter;
			while (true) {
				i -= u[t];
				j -= v[t];
				if (!isInside(i, j))
					break;
				if (a[i][j] != a[iCenter][jCenter])
					break;
				k++;
			}
			k++;
			if (k >= 5)
				while (k-- > 0) {
					i += u[t];
					j += v[t];
					if (i != iCenter || j != jCenter)
						lines.addElement(new Point(i, j));
				}
		}
		if (lines.size() > 0)
			lines.addElement(new Point(iCenter, jCenter));
		else
			lines = null;
		return lines;
	}
	
	public static Vector checkSquares(byte[][] a, int iCenter, int jCenter) {
		byte[] u = { -1, 0, 1, 1, 1, 0, -1, -1 };
		byte[] v = { -1, -1, -1, 0, 1, 1, 1, 0 };
		byte[] mark = { 0, 0, 0, 0, 0, 0, 0, 0 };
		byte color = a[iCenter][jCenter];
		int t = 0;
		for (int k = 0; k < 8; k++) {
			int x = iCenter + u[k];
			int y = jCenter + v[k];
			if (isInside(x, y) && a[x][y] == color) {
				t = t | (128 >> k);
				mark[k] = 1;
			}
		}
		switch (t) {
		case 193:
		case 112:
		case 7:
		case 28:
		case 241:
		case 124:
		case 31:
		case 199:
			Vector squares = new Vector();
			squares.addElement(new Point(iCenter, jCenter));
			for (int k = 0; k < 8; k++) {
				if (mark[k] == 1) {
					squares.addElement(new Point(iCenter + u[k], jCenter + v[k]));
				}
			}
			return squares;
		}
		return null;
	}
	
	public static Vector checkBlocks(byte[][] a, int iCenter, int jCenter) {
		byte[] queuei = new byte[81];
		byte[] queuej = new byte[81];
		
		boolean[][] mark = new boolean[9][9];
		
		byte[] u = { 1, 0, -1, 0 };
		byte[] v = { 0, 1, 0, -1 };
		
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++)
				mark[i][j] = true;
		mark[iCenter][jCenter] = false;
		byte color = a[iCenter][jCenter];

		byte fist = 0, last = 0;
		queuei[fist] = (byte) iCenter;
		queuej[fist] = (byte) jCenter;
		
		Vector blocks = new Vector();
		blocks.addElement(new Point(iCenter, jCenter));
		
		while (fist <= last) {
			int x = queuei[fist];
			int y = queuej[fist];
			fist++;
			for (int k = 0; k < 4; k++) {
				byte xx = (byte) (x + u[k]);
				byte yy = (byte) (y + v[k]);
				if (!isInside(xx, yy)) continue;
				if (mark[xx][yy] && a[xx][yy] == color) {
					last++;
					queuei[last] = xx;
					queuej[last] = yy;
					mark[xx][yy] = false;
					blocks.addElement(new Point(xx, yy));
				}
			}
		}
		if (blocks.size() < 7)
			return null;
		else
			return blocks;
	}

	public static Vector merge(Vector l1, Vector l2) {
		for (int i = l2.size() - 1; i >= 0; i--) {
			Point p = (Point) l2.elementAt(i);
			if (!checkExist(l1, p))
				l1.addElement(p);
		}
		return l1;
	}

	public static boolean checkExist(Vector l, Point p) {
		for (int i = l.size() - 1; i >= 0; i--) {
			Point pp = (Point) l.elementAt(i);
			if (pp.x == p.x && pp.y == p.y)
				return true;
		}
		return false;
	}

	private static boolean isInside(int i, int j) {
		return (i >= 0 && i < 9 && j >= 0 && j < 9);
	}
	
	public static int calcuScore(int balls, int min) {
		if (balls < min) return 0;
		return min + (balls - min) * 2;
	}
	
	public static int makeNumber(String bits) {
		if (bits.length() != 8) return 0;
		int b = 0;
		for (byte i = 0; i <= 7; i++)
			if (bits.charAt( 7 - i) == '1')
				b = b | (1 << i);
		return b;
	}

}
